#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import bs4
import requests
import utils

home = 'https://baike.baidu.com/item/'

def relations(name, exclude=None):
    url = home + name
    soup = utils.url2soup(url, 
        headers={'user-agent':''})
    x = soup.find('div', {'id': "slider_relations"})
    if not x:
        return []
    if exclude:
        return [a.em.text for a in x.find_all('li') if a.em.text not in exclude]
    else:
        return [a.em.text for a in x.find_all('li')]


def search(start, goal, deg=7):
    # start = '杨幂'
    paths =[[start]]
    visited = [start]

    for _ in range(deg):
        new_paths = []
        for p in paths:
            print('-'.join(p))
            start = p[-1]
            for r in relations(start, visited):
                if r == goal:
                    return p + [r]
                pc = p.copy()
                pc.append(r)
                new_paths.append(pc)
                visited.append(r)
        paths = new_paths
    else:
        raise 'No relations!'

print('-'.join(search('杨紫', '赵丽颖')))
